//字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。 
//
// 示例 1： 
//
// 
// 输入：s1 = "waterbottle", s2 = "erbottlewat"
// 输出：True
// 
//
// 示例 2： 
//
// 
// 输入：s1 = "aa", s2 = "aba"
// 输出：False
// 
//
// 
// 
//
// 提示： 
//
// 
// 字符串长度在[0, 100000]范围内。 
// 
//
// 说明: 
//
// 
// 你能只调用一次检查子串的方法吗？ 
// 
//
// Related Topics 字符串 字符串匹配 👍 260 👎 0


package LeetCode.editor.cn;


/**
 * @author ldltd
 * @date 2025-06-12 09:46:24
 * @description 面试题 01.09.字符串轮转
 
 */
 
public class StringRotationLcci {
    public static void main(String[] args) {
    //测试代码
    StringRotationLcci fun = new StringRotationLcci();
    Solution solution= fun.new Solution();
    solution.isFlipedString("waterbottle", "erbottlewat");
    }

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isFlipedString1(String s1, String s2) {
        if(s1.equals(s2)) return true;
        for (int i = 1; i < s1.length(); i++) {
            String s = s1.substring(i, s1.length()) + s1.substring(0, i);
            if(s.equals(s2)) {
                return true;
            }
        }
        return false;
    }
    public boolean isFlipedString2(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
     int N = 200010, P = 13131;
     int[] h = new int[N], p = new int[N];
    /*若两字符串互为旋转，则「其一字符串」必然为「另一字符串拓展两倍长度后（循环子串）」的子串。
    基于此，我们可以使用「字符串哈希」进行求解：先计算 s2 的字符串哈希值 t，
    然后构造出 s1 + s1 的哈希数组和次方数组，
    在两数组中检查是否存在长度为 n 的连续子段的哈希值 cur 与 t 相等。

    为什么需要平方数组
    h[j] - h[i - 1] * p[j - i + 1] 的计算方式是为了得到 s1 + s1 中从 i 到 j 的子串的哈希值。
    如P=131  s='abc'
    h1 = a
    h2= a*P + b
    h3= a*P^2 + b*P + c
    计算 'bc' 的哈希值时，b*P + c 的部分需要减去 a*P^2，
    h3-h1*p^2=(ap^2 + b*P + c) - (a*P^2) = b*P + c

    为什么选择 P = 13131？
    P 是一个大质数，用于减少哈希冲突。

    经验值：常用 131、13331、13131 等质数，具体选择取决于字符串的字符分布。
    */
    public boolean isFlipedString3(String s1, String s2) {
        if (s1.length() != s2.length()) return false;
        int n = s1.length();
        for (int i = 1; i <= n; i++)
            h[i] = h[i - 1] * P + s2.charAt(i - 1);
        int t = h[n]; // s2 hash
        s1 = s1 + s1;
        p[0] = 1;
        for (int i = 1; i <= 2 * n; i++) {
            h[i] = h[i - 1] * P + s1.charAt(i - 1);
            p[i] = p[i - 1] * P;
        }
        for (int i = 1; i + n - 1 <= 2 * n; i++) {
            int j = i + n - 1, cur = h[j] - h[i - 1] * p[j - i + 1];
            if (cur == t) return true;
        }
        return false;
    }
    // 使用滚动哈希优化
    public boolean isFlipedString(String s1, String s2) {
        int P = 13131;
        if (s1.length() != s2.length()) return false;
        if (s1.equals(s2)) return true;
        int n = s1.length();
        int t = 0;
        for (int i = 1; i <= n; i++) t = t * P + s2.charAt(i - 1);
        int hl = 0, hr = 0, p = P;
        for (int i = 1; i < n; i++) {
            hr = hr * P + s1.charAt(i - 1);
            p *= P;
        }
        for (int i = n; i <= 2 * n; i++) {
            int j = i - n + 1;
            hr = hr * P + s1.charAt((i - 1) % n);
            int cur = hr - hl * p;
            if (cur == t) return true;
            hl = hl * P + s1.charAt((j - 1) % n);
        }
        return false;
    }



}
//leetcode submit region end(Prohibit modification and deletion)

}
